package com.cb2.algorithm.leetcode;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree'>找出克隆二叉树中的相同节点(Find a Corresponding Node of a Binary Tree in a Clone of That Tree)</a>
 * <p>给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。</p>
 * <p>其中，克隆树 cloned 是原始树 original 的一个 副本 。</p>
 * <p>请找出在树 cloned 中，与 target 相同 的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。</p>
 * <p>注意：你 不能 对两棵二叉树，以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: tree = [7,4,3,null,null,6,19], target = 3
 *      输出: 3
 *      解释: 上图画出了树 original 和 cloned。target 节点在树 original 中，用绿色标记。答案是树 cloned 中的黄颜色的节点（其他示例类似）。
 *
 * 示例 2:
 *      输入: tree = [7], target =  7
 *      输出: 7
 *
 * 示例 3:
 *      输入: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
 *      输出: 4
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数量范围为 [1, 10^4] 。</li>
 *     <li>同一棵树中，没有值相同的节点。</li>
 *     <li>target 节点是树 original 中的一个节点，并且不会是 null 。</li>
 * </ul>
 * </p>
 *
 * <p>
 * <b>进阶：如果树中允许出现值相同的节点，将如何解答？</b>
 * </p>
 *
 * @author c2b
 * @since 2023/11/20 16:04
 */
public class LC1379FindCorrespondingNodeOfBinaryTreeInCloneOfThatTree_S {

    static class Solution {
        // 如果不存在重复值，直接使用值进行比较
        /**
         * 深度优先遍历
         */
        public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
            return getTargetCopyByDFSWithNoDuplicateValue(cloned, target.val);
            //return getTargetCopyByBFSWithNoDuplicateValue(cloned, target.val);

            //return dfs(original, cloned, target);
            //return bfs(original, cloned, target);
        }

        /**
         * 深度优先遍历
         */
        private TreeNode getTargetCopyByDFSWithNoDuplicateValue( TreeNode currNode, int targetVal) {
            if (currNode == null) {
                return null;
            }
            if (currNode.val == targetVal) {
                return currNode;
            }
            TreeNode left = getTargetCopyByDFSWithNoDuplicateValue(currNode.left, targetVal);
            return left != null ? left : getTargetCopyByDFSWithNoDuplicateValue(currNode.right, targetVal);
        }

        private TreeNode getTargetCopyByBFSWithNoDuplicateValue( TreeNode cloned, int targetVal) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(cloned);
            while (!queue.isEmpty()) {
                TreeNode currNode = queue.poll();
                if (currNode.val == targetVal) {
                    return currNode;
                }
                if (currNode.left != null) {
                    queue.offer(currNode.left);
                }
                if (currNode.right != null) {
                    queue.offer(currNode.right);
                }
            }
            return null;
        }


        /**
         * 广度优先遍历
         */
        private TreeNode bfs(final TreeNode original, final TreeNode cloned, final TreeNode target) {
            Queue<TreeNode> queue1 = new LinkedList<>();
            Queue<TreeNode> queue2 = new LinkedList<>();
            queue1.offer(original);
            queue2.offer(cloned);
            while (queue1.size() > 0) {
                TreeNode node1 = queue1.poll();
                TreeNode node2 = queue2.poll();
                if (node1 == target) {
                    return node2;
                }
                if (node1.left != null) {
                    queue1.offer(node1.left);
                    queue2.offer(node2.left);
                }
                if (node1.right != null) {
                    queue1.offer(node1.right);
                    queue2.offer(node2.right);
                }
            }
            return null;
        }

        /**
         * 如果树中存在重复值
         */
        public final TreeNode dfs(final TreeNode original, final TreeNode cloned, final TreeNode target) {
            if (original == null) {
                return null;
            }
            if (original == target) {
                return cloned;
            }
            TreeNode left = dfs(original.left, cloned.left, target);
            return left != null ? left : dfs(original.right, cloned.right, target);
        }

        /**
         * 如果树中存在重复值
         */
        public final TreeNode getTargetCopy2(final TreeNode original, final TreeNode cloned, final TreeNode target) {
            int idx = getTargetIdx(original, target, 1); // 求取目标结点的索引
            return findTarget(cloned, target, 1, idx); // 根据索引在cloned树中寻找
        }

        /**
         * 目标节点在树中的下标位置。层序遍历从1开始的下标位置
         */
        private int getTargetIdx(TreeNode root, TreeNode target, int nowIdx) {
            if (root == null) {
                return -1;
            }
            if (root == target) {
                return nowIdx;
            }
            // 先去左子树上查找，未找到再去右子树中差值。左子树的下标当前节点的idx*2；右子树的下标为当前节点的idx*2 + 1
            int lIdx = getTargetIdx(root.left, target, nowIdx * 2);
            return lIdx != -1 ? lIdx : getTargetIdx(root.right, target, nowIdx * 2 + 1);
        }

        private TreeNode findTarget(TreeNode curr, TreeNode target, int nowIdx, int tarIdx) {
            if (curr == null) {
                return null;
            }
            if (curr.val == target.val && nowIdx == tarIdx) {
                return curr;
            }
            // 在左子数中继续查找
            TreeNode left = findTarget(curr.left, target, nowIdx * 2, tarIdx);
            // 在右子树中继续查找
            return left != null ? left : findTarget(curr.right, target, nowIdx * 2 + 1, tarIdx);
        }
    }
}
